import java.util.PriorityQueue;

/**
 * LeetCode 23. 合并K个升序链表
 */
public class Solution_23 {
    /**
     * 方法三：小根堆
     * <p>
     * 时间复杂度：O(nk * logk)，k 为链表的个数，n 为链表平均长度；
     * 
     * 共 nk 个节点，每个节点插入和删除时间为 O(logk)
     * <p>
     * 空间复杂度：O(k)，堆空间
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> heap 
            = new PriorityQueue<>(lists.length, (l1, l2) -> l1.val - l2.val);
        for (ListNode listNode : lists) {
            if (listNode != null) {
                heap.offer(listNode);
            }
        }

        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        while (!heap.isEmpty()) {
            cur.next = heap.poll();
            cur = cur.next;
            if (cur.next != null) {
                heap.offer(cur.next);
            }
        }
        return dummyHead.next;
    }

    /**
     * 方法二：分治合并
     * <p>
     * 方法一的优化，采用分治的思路
     * <p>
     * 时间复杂度：O(nk * logk)，k 为链表的个数，n 为链表平均长度
     * <p>
     * 空间复杂度：O(logk)，递归空间
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    /**
     * 合并链表数组中索引为 [left..right] 的链表（双闭区间）
     * <p>
     * 数组中的链表均为有序链表
     */
    public ListNode merge(ListNode[] lists, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    /**
     * 方法一：顺序合并
     * <p>
     * 遍历数组，每次合并一个链表
     * <p>
     * 时间复杂度：O(k^2 * n)，k 为链表的个数，n 为链表平均长度
     * <p>
     * 空间复杂度：O(1)
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        ListNode ans = null;
        for (ListNode listNode : lists) {
            ans = mergeTwoLists(ans, listNode);
        }
        return ans;
    }

    /**
     * 合并两个有序链表
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 == null) ? l2 : l1;
        return dummyHead.next;
    }
}
